

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">

<html>


<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">

<base target="_top">
<style type="text/css">
  

/* default css */

table {
  font-size: 1em;
  line-height: inherit;
  border-collapse: collapse;
}


tr {
  
  text-align: left;
  
}


div, address, ol, ul, li, option, select {
  margin-top: 0px;
  margin-bottom: 0px;
}

p {
  margin: 0px;
}


pre {
  font-family: Courier New;
  white-space: pre-wrap;
  margin:0;
}

body {
  margin: 6px;
  padding: 0px;
  font-family: Verdana, sans-serif;
  font-size: 10pt;
  background-color: #ffffff;
  color: #000;
}


img {
  -moz-force-broken-image-icon: 1;
}

@media screen {
  html.pageview {
    background-color: #f3f3f3 !important;
    overflow-x: hidden;
    overflow-y: scroll;
  }

  

  body {
    min-height: 1100px;
    
    counter-reset: __goog_page__;
  }
  
  * html body {
    height: 1100px;
  }
  /* Prevent repaint errors when scrolling in Safari. This "Star-7" css hack
     targets Safari 3.1, but not WebKit nightlies and presumably Safari 4.
     That's OK because this bug is fixed in WebKit nightlies/Safari 4 :-). */
  html*#wys_frame::before {
    content: '\A0';
    position: fixed;
    overflow: hidden;
    width: 0;
    height: 0;
    top: 0;
    left: 0;
  }
  
  .pageview body {
    border-top: 1px solid #ccc;
    border-left: 1px solid #ccc;
    border-right: 2px solid #bbb;
    border-bottom: 2px solid #bbb;
    width: 648px !important;
    margin: 15px auto 25px;
    padding: 40px 50px;
  }
  /* IE6 */
  * html {
    overflow-y: scroll;
  }
  * html.pageview body {
    overflow-x: auto;
  }
  

  
    
    .writely-callout-data {
      display: none;
    }
    

    .writely-footnote-marker {
      background-image: url('MISSING');
      background-color: transparent;
      background-repeat: no-repeat;
      width: 7px;
      overflow: hidden;
      height: 16px;
      vertical-align: top;

      
      -moz-user-select: none;
    }
    .editor .writely-footnote-marker {
      cursor: move;
    }
    .writely-footnote-marker-highlight {
      background-position: -15px 0;
      -moz-user-select: text;
    }
    .writely-footnote-hide-selection ::-moz-selection, .writely-footnote-hide-selection::-moz-selection {
      background: transparent;
    }
    .writely-footnote-hide-selection ::selection, .writely-footnote-hide-selection::selection {
      background: transparent;
    }
    .writely-footnote-hide-selection {
      cursor: move;
    }

    /* Comments */
    .writely-comment-yellow {
      background-color: #ffffd7;
    }
    .writely-comment-orange {
      background-color: #ffe3c0;
    }
    .writely-comment-pink {
      background-color: #ffd7ff;
    }
    .writely-comment-green {
      background-color: #d7ffd7;
    }
    .writely-comment-blue {
      background-color: #d7ffff;
    }
    .writely-comment-purple {
      background-color: #eed7ff;
    }

  


  
  .br_fix span+br:not(:-moz-last-node) {
    
    position:relative;
    
    left: -1ex
    
  }

  
  #cb-p-tgt {
    font-size: 8pt;
    padding: .4em;
    background-color: #ddd;
    color: #333;
  }
  #cb-p-tgt-can {
    text-decoration: underline;
    color: #36c;
    font-weight: bold;
    margin-left: 2em;
  }
  #cb-p-tgt .spin {
    width: 16px;
    height: 16px;
    background: url(//ssl.gstatic.com/docs/clipboard/spin_16o.gif) no-repeat;
  }
}

h6 { font-size: 8pt }
h5 { font-size: 8pt }
h4 { font-size: 10pt }
h3 { font-size: 12pt }
h2 { font-size: 14pt }
h1 { font-size: 18pt }

blockquote {padding: 10px; border: 1px #DDD dashed }

.webkit-indent-blockquote { border: none; }

a img {border: 0}

.pb {
  border-width: 0;
  page-break-after: always;
  /* We don't want this to be resizeable, so enforce a width and height
     using !important */
  height: 1px !important;
  width: 100% !important;
}

.editor .pb {
  border-top: 1px dashed #C0C0C0;
  border-bottom: 1px dashed #C0C0C0;
}

div.google_header, div.google_footer {
  position: relative;
  margin-top: 1em;
  margin-bottom: 1em;
}


/* Table of contents */
.editor div.writely-toc {
  background-color: #f3f3f3;
  border: 1px solid #ccc;
}
.writely-toc > ol {
  padding-left: 3em;
  font-weight: bold;
}
ol.writely-toc-subheading {
  padding-left: 1em;
  font-weight: normal;
}
/* IE6 only */
* html writely-toc ol {
  list-style-position: inside;
}
.writely-toc-none {
  list-style-type: none;
}
.writely-toc-decimal {
  list-style-type: decimal;
}
.writely-toc-upper-alpha {
  list-style-type: upper-alpha;
}
.writely-toc-lower-alpha {
  list-style-type: lower-alpha;
}
.writely-toc-upper-roman {
  list-style-type: upper-roman;
}
.writely-toc-lower-roman {
  list-style-type: lower-roman;
}
.writely-toc-disc {
  list-style-type: disc;
}

/* Ordered lists converted to numbered lists can preserve ordered types, and
   vice versa. This is confusing, so disallow it */
ul[type="i"], ul[type="I"], ul[type="1"], ul[type="a"], ul[type="A"] {
  list-style-type: disc;
}

ol[type="disc"], ol[type="circle"], ol[type="square"] {
  list-style-type: decimal;
}

/* end default css */


  /* default print css */
  @media print {
    body {
      padding: 0;
      margin: 0;
    }

    div.google_header, div.google_footer {
      display: block;
      min-height: 0;
      border: none;
    }

    div.google_header {
      flow: static(header);
    }

    /* used to insert page numbers */
    div.google_header::before, div.google_footer::before {
      position: absolute;
      top: 0;
    }

    div.google_footer {
      flow: static(footer);
    }

    /* always consider this element at the start of the doc */
    div#google_footer {
      flow: static(footer, start);
    }

    span.google_pagenumber {
      content: counter(page);
    }

    span.google_pagecount {
      content: counter(pages);
    }

    .endnotes {
      page: endnote;
    }

    /* MLA specifies that endnotes title should be 1" margin from the top of the page. */
    @page endnote {
      margin-top: 1in;
    }

    callout.google_footnote {
      
      display: prince-footnote;
      footnote-style-position: inside;
      /* These styles keep the footnote from taking on the style of the text
         surrounding the footnote marker. They can be overridden in the
         document CSS. */
      color: #000;
      font-family: Verdana;
      font-size: 10.0pt;
      font-weight: normal;
    }

    /* Table of contents */
    #WritelyTableOfContents a::after {
      content: leader('.') target-counter(attr(href), page);
    }

    #WritelyTableOfContents a {
      text-decoration: none;
      color: black;
    }

    /* Comments */
    .writely-comment-yellow {
      background-color: #ffffd7;
    }
    .writely-comment-orange {
      background-color: #ffe3c0;
    }
    .writely-comment-pink {
      background-color: #ffd7ff;
    }
    .writely-comment-green {
      background-color: #d7ffd7;
    }
    .writely-comment-blue {
      background-color: #d7ffff;
    }
    .writely-comment-purple {
      background-color: #eed7ff;
    }
  }

  @page {
    @top {
      content: flow(header);
    }
    @bottom {
      content: flow(footer);
    }
    @footnotes {
      border-top: solid black thin;
      padding-top: 8pt;
    }
  }
  /* end default print css */


/* custom css */


/* end custom css */

/* ui edited css */

body {
  font-family: Verdana;
  
  font-size: 10.0pt;
  line-height: normal;
  background-color: #ffffff;
}
/* end ui edited css */


/* editor CSS */
.editor a:visited {color: #551A8B}
.editor table.zeroBorder {border: 1px dotted gray}
.editor table.zeroBorder td {border: 1px dotted gray}
.editor table.zeroBorder th {border: 1px dotted gray}


.editor div.google_header, .editor div.google_footer {
  border: 2px #DDDDDD dashed;
  position: static;
  width: 100%;
  min-height: 2em;
}

.editor .misspell {background-color: yellow}

.editor .writely-comment {
  font-size: 9pt;
  line-height: 1.4;
  padding: 1px;
  border: 1px dashed #C0C0C0
}


/* end editor CSS */

</style>

  
  <title>W11 Niezawodne systemy rozproszone</title>

</head>

<body 
    
    >
    
    
    
<div id=kchi style=TEXT-ALIGN:left>
  <b style=COLOR:#3d85c6><font size=5>Niezawodne systemy rozproszone</font></b><br>
  <hr size=2><br>
  <b style=COLOR:#3d85c6><font size=3>Tolerowanie awarii</font></b><br>
  <hr size=2><br>
  <div id=uapp style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_25876kz56mgm_b.png" style=HEIGHT:342px;WIDTH:500px><br>
    <br>
    Systemy rozproszone potencjalnie mogą charakteryzować się wyższą odpornością na awarie. Wynika to z rozproszenia i być może zwielokrotnienia pewnych zasobów. Awaria częściowa (ang. <i>partial</i> <i>failure</i> ) może w systemie rozproszonym spowodować uszkodzenie pojedynczej składowej systemu, która może być zastąpiona inną i nie musi powodować zatrzymania całego systemu. W systemach scentralizowanych awaria częściowa z reguły powoduje unieruchomienie całej aplikacji.<br>
    <br>
    <p>
      Większa odporność na awarie systemów rozproszonych jest tylko potencjalna i wymaga zastosowania różnych dodatkowych mechanizmów w celu automatycznego podejmowania czynności naprawczych w przypadku stwierdzeni awarii. Uodpornienie procesów może powodować, że awaria jednych nie będzie propagowała się na inne procesy. Problem ten pojawia się np. w kontekście komunikacji, szczególnie przy realizacji niezawodnego rozsyłania do grupy procesów.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Ważną cechą wielu aplikacji jest niepodzielność. Dotyczy to np. realizacji transakcji, której poszczególne kroki powinny zostać wykonane w całości. Realizacja niepodzielności w systemie rozproszonym wymaga zastosowania rozproszonego zatwierdzania, które jest równoważne problemowi konsensusu.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Jeżeli w systemie dochodzi już do awarii (węzła, procesu) to można podjąć próby automatycznego usunięcia skutków takiej awarii. Można w tym celu zastosować metody odtwarzania w celu przywrócenia stanu systemu rozproszonego sprzed awarii.
    </p>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>System wiarygodny</font></b><br>
    <hr size=2><br>
    <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-11-wyk-1.0-Slajd1 title=Sr-11-wyk-1.0-Slajd1> </a>
    <div id=dp68 style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2588dxf6n9hd_b.png" style=HEIGHT:343px;WIDTH:500px><br>
      <br>
      Niezawodność systemu wiąże się z nieco ogólniejszą koncepcją systemów wiarygodnych (ang. <i>dependable</i> <i>systems</i> ). Wiarygodność systemu oznacza w ogólności pewność działania systemu, która pozwala mieć uzasadnione zaufanie do usług, które ten system dostarcza. Konkretyzując tą definicję można wymienić następujące szczegółowe oczekiwania względem systemu: dostępność, niezawodność, pewność i pielęgnowalność.<br>
      <br>
      <p>
        <b>Dostępność</b> (ang. <i>availablility</i> ) jest gotowością systemu do natychmiastowego działania. Jest opisywana prawdopodobieństwem, że w dowolnej chwili system jest w stanie spełniać swoje funkcje.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        <b>Niezawodność</b> (ang. <i>reliability</i> ) oznacza zdolność do ciągłego działania. W przeciwieństwie do dostępności, opis niezawodności odnosi się do przedziału czasu a nie do pojedynczego momentu. System, który wyłącza się na 1ms co godzinę ma dostępność na poziomie 99,9999%, ale jest bardzo zawodny. System, który jest niezawodny, ale jest wyłączany raz do roku na 2 tygodnie ma dostępność na poziomie 96%.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        <b>Pewność</b> (ang. <i>safety</i> ) oznacza, że chwilowa awaria pojedynczego komponentu nie powoduje katastrofalnych skutków.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        <b>Pielęgnowalność</b> (ang. <i>maintainability</i> ) dotyczy łatwości naprawiania uszkodzonego systemu. Wysoka pielęgnowalność ułatwia osiągnięcie wysokiej dostępności, ponieważ awarie mogą być automatycznie wykrywane i usuwane.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Jednocześnie od systemów wiarygodnych oczekuje się, że będą one <b>bezpieczne</b> (ang. <i>security</i> ).
      </p>
      <br>
      <br>
      <b style=COLOR:#3d85c6><font size=3>Podstawowe definicje</font></b><br>
      <hr size=2><br>
      <div id=hpd1 style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2589c7h9x4d8_b.png" style=HEIGHT:341px;WIDTH:500px><br>
        <br>
        System komputerowy <b>zawodzi</b> (ang. <i>fails</i> ) gdy jego działanie przestaje być zgodne ze specyfikacją, a więc np. jedna z usług przestaje być dostępna.
        <p>
          <br>
        </p>
        <p>
          <b>Błąd</b> (ang. <i>error</i> ) jest częścią stanu systemu, wskutek którego może dojść do awarii. Błędy mogą się pojawiać np. podczas transmisji danych lub podczas wykonywania operacji arytmetycznych.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          <b>Wada</b> (ang. <i>fault</i> ) to przyczyna błędu. Znalezienie przyczyny błędu jest warunkiem koniecznym skutecznego usunięcia błędów w przyszłości.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          Konsekwencją wystąpienia błędu jest <b>awaria</b> (ang. <i>failure</i> ) systemu. Awaria oznacza widoczną niezdolność systemu lub jego składowej do wykonywania wymaganej funkcji w określonych granicach.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          Ponieważ wiele wad jest efektem zewnętrznych przyczyn, niezależnych i niekontrolowanych przez system (np. pogoda), konieczne staje się ich kontrolowanie. Można to realizować poprzez zapobieganie ich występowaniu, usuwanie wad lub ich przewidywanie. W praktyce istotna jest możliwość <b>tolerowania</b> <b>awarii</b> (ang. <i>fault</i> <i>tolerance</i> ), a więc możliwości świadczenia usług pomimo występowania wad.
        </p>
        <br>
        <br>
        <b style=COLOR:#3d85c6><font size=3>Klasyfikacja wad</font></b><br>
        <hr size=2><a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-11-wyk-1.0-Slajd3 title=Sr-11-wyk-1.0-Slajd3> </a><br>
      </div>
      <div id=cz.8 style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2590px6h7pwc_b.png" style=HEIGHT:341px;WIDTH:500px><br>
        <br>
        Wady, a więc przyczyny pojawiających się w systemie błędów, mogą być bardzo różne. W zależności od ich charakteru należy przedsięwziąć różne środki zaradcze stąd ważna jest klasyfikacja różnych typów wad.<br>
        <br>
        <p>
          <b>Wady</b> <b>przejściowe</b> (ang. <i>transient</i> <i>faults</i> ) pojawiają się i znikają, mają charakter przejściowy. Właściwym sposobem postępowania z tego typu wadami jest powtórzenie operacji, ponieważ sytuacja taka może już nigdy nie wystąpić. Tego typu wady mogą się pojawić w wyniku przejściowych warunków pogodowych lub w wyniku pojawienia się przejściowych zakłóceń ze strony zewnętrznych urządzeń czy zwierząt.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          <b>Wady</b> <b>nieciągłe</b> (ang. <i>intermittent</i> <i>faults</i> ) również pojawiają się i znikają, ale ich cechą charakterystyczną są nawroty. Przykładem tego typu wady może być np. luźny styk. Wady tego typu są trudne do wykrycia, ponieważ mogą nie pojawiać się podczas monitorowania systemu w celu ich detekcji.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          <b>Wady</b> <b>trwałe</b> (ang. <i>permanent</i> <i>faults</i> ) nie znikają do momentu ich naprawy. Jest to wynikiem np. uszkodzenia jakiegoś podzespołu lub błędu w oprogramowaniu.
        </p>
        <br>
        <br>
        <b style=COLOR:#3d85c6><font size=3>Modele awarii</font></b><br>
        <hr size=2><a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-11-wyk-1.0-Slajd4 title=Sr-11-wyk-1.0-Slajd4> </a><br>
        <div id=zzll style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2591cz6xrvfw_b.png" style=HEIGHT:341px;WIDTH:500px><br>
          <br>
          System, który ulega awarii przestaje świadczyć usługi. Nie zawsze jednak powodem awarii jest ten serwer, do którego kierowane jest bezpośrednio żądanie. Możliwe jest bowiem, że serwer ten jest blokowany brakiem dostępu do usług innych serwerów i z tego powodu nie daje odpowiedzi. Dla lepszego zrozumienia różnych typów awarii zaproponowano kilka kategorii. Slajd przedstawia jedną z takich klasyfikacji.
          <p>
            <br>
          </p>
          <p>
            Awaria typu <b>załamanie</b> (ang. <i>crash</i> <i>failure</i> ) oznacza trwałe załamanie systemu, który do tej pory działał poprawnie. W praktyce oznacza to np. zawieszenie systemu operacyjnego.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            <b>Błąd</b> <b>ominięcia</b> (ang. <i>omission</i> <i>failure</i> ) oznacza brak odpowiedzi ze strony serwera. Błąd taki może oznaczać, że żądanie nie dociera do serwera lub nie jest w nim obsługiwane. Tego typu sytuacja nie zakłóca pracy serwera, ponieważ brak żądania nie zmienia stanu serwera. Innym możliwym powodem braku odpowiedzi z serwera jest problem z dostarczeniem odpowiedzi na żądanie klienta. Serwer w takiej sytuacji odbiera żądanie, przetwarza je i próbuje wysłać odpowiedź, która jednak z różnych powodów nie dociera do klienta. Sytuacja taka wymaga od serwera, aby był przygotowany na powtórne przesłanie tego samego żądania przez klienta.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Kolejną kategorię stanowią <b>awarie</b> <b>odliczania</b> <b>czasu</b> (ang. <i>timing</i> <i>failures</i> ) oznaczające brak odpowiedzi ze strony serwera w określonym przedziale czasowym. Dotyczy to zarówno odpowiedzi przychodzących zbyt szybko (klient może być niegotowy na odbiór wiadomości) lub – co jest sytuacją bardziej typową – odpowiedź przychodzi zbyt późno. W drugim przypadku mówimy również o <i>awariach</i> <i>efektywności</i> .<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Kolejną kategorię stanowią <b>błędy</b> <b>odpowiedzi</b> (ang. <i>response</i> <i>failures</i> ), oznaczające błędną odpowiedź serwera. Błędna odpowiedź może być generowana w odpowiedzi na faktyczne żądanie klienta. Inna sytuacja może wystąpić w przypadku przesłania niepoprawnego czy niezrozumiałego przez serwer żądania. Może wtedy nastąpić <b>awaria</b> <b>zmiany</b> <b>stanu</b> (ang. <i>state</i> <i>transition</i> <i>failure</i> ). Polega ona na wykonaniu przez serwer niestandardowych działań, powodujących zmianę stanu serwera, która nie powinna nastąpić.
          </p>
          <br>
          <br>
          <div id=ssri style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2592hjbx9fgz_b.png" style=HEIGHT:341px;WIDTH:500px><br>
            <br>
            Najogólniejszą kategorią awarii są <b>awarie</b> <b>bizantyjskie</b> , zwane również <b>dowolnymi</b> (ang. <i>Byzantine</i> <i>failures</i> , <i>arbitrary</i> <i>failures</i> ). Awaria bizantyjska oznacza, że serwer może wygenerować całkowicie dowolną i niespodziewaną odpowiedź. Jego działanie może być nawet złośliwe i może angażować inne serwery w celu zafałszowywania odpowiedzi.<br>
            <br>
            <p>
              <b>Zatrzymanie</b> (ang. <i>stopping</i> <i>failure</i> ) oznacza, że serwer przestaje zwracać wyniki w sposób dający się stwierdzić przez inne procesy. Najłagodniejszą formą zatrzymania jest omówione wcześniej załamanie. Inną formą jest np. błąd ominięcia.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Serwery z reguły nie uprzedzają innych, że mają zamiar ulec awarii. Jest to szczególnie problematyczne w systemach z <b>awariami</b> <b>uciszającymi</b> (ang. <i>fail-silent</i> <i>systems</i> ). Procesy dokonując oceny pracy serwerów mogą dojść do przekonania, że uległy one awarii, pomimo że awaria jest tylko przejściowa i polega jedynie na zwolnieniu pracy, a więc na niedostatku efektywności.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Generowanie całkowicie losowych odpowiedzi przez serwer może być w stosunkowo prosty sposób wykryte przez procesy. Tego typu awaria jest awarią dowolną, ale o łagodnej formie. Mówimy, że jest to <b>awaria</b> <b>bezpieczna</b> (ang. <i>fail-safe</i> ).
            </p>
            <br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>Maskowanie awarii</font></b><br>
            <hr size=2>
          </div>
          <br>
        </div>
        <div id=g-6b style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2593fxv372gb_b.png" style=HEIGHT:341px;WIDTH:500px><br>
          <br>
          Tolerowanie awarii w praktyce oznacza ukrywanie (maskowanie) faktu ich występowania przed innymi procesami czy użytkownikami końcowymi. Podstawową metodą maskowania awarii jest zastosowanie nadmiarowości. Nadmiarowość może przyjmować różne formy: nadmiarowości informacji, czasu lub nadmiarowości fizycznej. <b>Nadmiarowość</b> <b>informacji</b> oznacza, że wymiana informacji realizowana jest z wykorzystaniem dodatkowych bitów umożliwiających odtworzenie informacji, która została zafałszowana. Przykładowo kod Hamminga umożliwia maskowanie szumów linii przesyłowej poprzez przesyłanie dodatkowych bitów korekcyjnych.<br>
          <br>
          <p>
            <b>Nadmiarowość</b> <b>czasu</b> polega na powieleniu wykonywania pewnych czynności w przypadku zajścia awarii. Przykładem mogą tu być transakcje. Wycofaną transakcję można ponownie zlecić systemowi do wykonania, licząc, że awaria, która spowodowała wcześniejsze wycofanie miała charakter przejściowy.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Ostatecznie <b>nadmiarowość</b> może być realizowana poprzez <b>fizyczne</b> zwielokrotnienie jednostek przetwarzających. Zwielokrotnienie takie może być realizowane zarówno sprzętowo jak i programowo. W przypadku zwielokrotnienia programowego mamy do czynienia <i>de</i> <i>facto</i> ze zwielokrotnieniem procesów. Zwielokrotnienie sprzętowe spotykane jest często w układach elektronicznych, które realizują przetwarzanie równolegle na tych samych danych i porównują wyniki w celu oszacowania poprawności działania układu.
          </p>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Odporność procesów - grupy procesów</font></b><br>
          <hr size=2><br>
          <div id=s4z5 style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2594hgz4nnkc_b.png" style=HEIGHT:342px;WIDTH:500px><br>
            <br>
            Tolerowanie wadliwego procesu jest możliwe poprzez zorganizowanie grupy procesów, które będą realizowały te same zadania i wzajemnie się kontrolowały. Zlecenia wysyłane do systemu będą przekazywane przez warstwę komunikacji grupowej realizującej niezawodne rozsyłanie wiadomości do wszystkich członków grupy. Awaria pojedynczego procesu nie wstrzyma w takiej sytuacji transmisji wiadomości do pozostałych procesów, co umożliwi przejęcie odpowiedzialności przez proces, który nadal jest poprawny.<br>
            <br>
            <p>
              Grupy są dynamiczne, co oznacza, że procesy mogą dołączać się do nich i odłączać podczas pracy systemu. Co więcej: procesy mogą w tym samym czasie należeć do kilku grup. Potrzebny jest więc mechanizm zarządzania grupami i przynależnością do nich.
            </p>
            <br>
            <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-11-wyk-1.0-Slajd8 title=Sr-11-wyk-1.0-Slajd8> </a><br>
            <b style=COLOR:#3d85c6><font size=3>Przynależność do grup</font></b><br>
            <hr size=2>
          </div>
          <br>
        </div>
        <div id=l1x9 style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2595c628gggk_b.png" style=HEIGHT:342px;WIDTH:500px><br>
          <br>
          Organizacja procesów w grupy oznacza, że trzeba zorganizować system zarządzania nimi, umożliwiający dołączanie nowych procesów do grupy, odłączanie od grupy i rozsyłanie komunikatów do grupy. Najprostszym podejściem jest zastosowanie <b>serwera</b> <b>grup</b> (ang. <i>group</i> <i>server</i> ), który centralnie przechowywałby pełną informację o utworzonych w systemie grupach i przynależności poszczególnych procesów do grup. Rozwiązanie to jakkolwiek koncepcyjnie proste i łatwe do zrealizowania, obarczone jest typowymi wadami podejścia scentralizowanego, a więc m.in. wrażliwością na awarie centralnego serwera. W rozwiązaniu rozproszonym dołączanie do grupy może być zrealizowane poprzez rozesłanie do wszystkich procesów odpowiedniego komunikatu informującego o dołączeniu do grupy. Trudniejsza jest jednakże realizacja odłączenia od grupy, szczególnie jeżeli jest ono następstwem zatrzymania procesu. W takiej sytuacji pozostałe procesy muszą po pierwsze stwierdzić fakt awarii jednego z członków grupy, a po drugie muszą wspólnie podjąć decyzję o usunięciu takiego procesu z grupy.<br>
          <br>
          <p>
            Oddzielną kwestią jest synchronizacja operacji dołączania i odłączania procesów do/z grup z jednocześnie zachodzącą wymianą komunikatów. Proces, który dołącza się do grupy powinien zacząć odbierać wszystkie komunikaty kierowane do niego, a proces, który odłącza się od grupy powinien przestać otrzymywać tego typu komunikaty. Osiągnięcie tej synchronizacji jest możliwe poprzez wykorzystanie mechanizmów komunikacji grupowej do samego zarządzania członkowstwem.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Rozproszone zarządzanie grupą może doprowadzić do sytuacji, kiedy procesy stwierdzą, że grupa uległa tak rozlicznym awariom, że dalsze jej funkcjonowanie wymaga rekonstrukcji. Działanie takie może być zainicjowane przez wiele procesów jednocześnie, co wymaga dodatkowej koordynacji.
          </p>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Maskowanie awarii i zwielokrotnianie</font></b><br>
          <hr size=2><br>
          <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-11-wyk-1.0-Slajd9 title=Sr-11-wyk-1.0-Slajd9> </a>
          <div id=f62m style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2596hn2kbnfs_b.png" style=HEIGHT:343px;WIDTH:500px><br>
            <br>
            Maskowanie awarii odbywa się poprzez organizowanie grup procesów i rozsyłanie do nich wszystkich w sposób niezawodny komunikatów. Wymaga to zastosowania zwielokrotnienia procesów, co może być realizowane na dwa podstawowe sposoby: poprzez protokoły oparte na kopii podstawowej lub poprzez protokoły zwielokrotnionych zapisów.<br>
            <br>
            <p>
              <b>Protokoły</b> <b>oparte</b> <b>na</b> <b>kopii</b> <b>podstawowej</b> stosują najczęściej model <b>podstawa-zapas</b> (ang. <i>primary-backup</i> ), w którym wszystkie modyfikacje przetwarzane są najpierw przez wybrany węzeł koordynujący, a następnie propagowane do pozostałych węzłów. Odczyty mogą być realizowane współbieżnie przez dowolny węzeł będący kopią serwera podstawowego. Procesy są więc zorganizowane w postaci hierarchicznej grupy z wyróżnionym węzłem-koordynatorem. Wadą takiego rozwiązania jest oczywiście ryzyko awarii węzła-koordynatora. W takiej sytuacji należy wykonać algorytm elekcji i dokonać wyboru nowego węzła-koordynatora spośród kopii zapasowych.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              <b>Protokoły</b> <b>zwielokrotnionych</b> <b>zapisów</b> działają na zasadzie <b>aktywnego</b> <b>zwielokrotniania</b> (ang. <i>active</i> <i>replication</i> ) lub poprzez dobieranie <b>kworum</b> . W obu podejściach procesy są zorganizowane w równouprawnioną grupę. W aktywnym zwielokrotnianiu wszystkie żądania (również zapisy) przesyłane są w identycznej postaci do wszystkich węzłów i przetwarzane współbieżnie. Algorytmy oparte na kworum wymagają wykonania modyfikacji przez procesy tworzące kworum. Zaletą protokołów zwielokrotnionych zapisów jest brak elementu centralnego przetwarzania, ale pojawia się w nich dodatkowy koszt związany z rozproszoną koordynacją.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Istotną kwestią jest liczba replik procesów, jakie będą tworzone w systemie. Mówimy, że system jest w stanie tolerować <i>k</i> uszkodzeń, gdy jego funkcjonowanie będzie nadal poprawne po wystąpieniu <i>k</i> awarii. Osiągnięcie takiego poziomu odporności zależy od charakteru awarii występujących w systemie. Jeżeli awarie mają charakter uciszający, to do tolerowania <i>k</i> awarii wystarczy <i>k+1</i> procesów. Proces <i>k+1</i> będzie w stanie udzielić odpowiedzi po awarii <i>k</i> procesów. W przypadku awarii bizantyjskich, w najgorszym przypadku <i>k</i> błędnie działających procesów może generować złą, ale spójną odpowiedź. Stwierdzenie tego faktu jest możliwe pod warunkiem posiadania dostępu do <i>k+1</i> poprawnych węzłów. W efekcie do tolerowania <i>k</i> awarii bizantyjskich potrzeba <i>2k+1</i> węzłów.
            </p>
            <br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>Uzgodnienia w systemach wadliwych</font></b><br>
            <hr size=2><br>
          </div>
          <div id=g0oa style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2597g3k535gd_b.png" style=HEIGHT:341px;WIDTH:500px><br>
            <br>
            Klient, podejmując decyzje na podstawie odpowiedzi z serwerów, może tolerować <i>k</i> awarii jeżeli ma dostęp do <i>2k+1</i> serwerów. Problem staje się jednak bardziej złożony gdy grupa procesów ma osiągnąć porozumienie. Porozumienie polega na podjęciu wspólnej decyzji i decyzja ta ma być podjęta w skończonej liczbie kroków. Z problemem uzgadniania mamy bardzo często do czynienia. Np. wybór koordynatora potrzebnego do pracy wielu algorytmów rozproszonych jest pewnego rodzaju porozumieniem. Zatwierdzenie bądź odrzucenie operacji atomowej wykonywanej w systemie rozproszonym (np. transakcji) również wymaga uzgodnienia. Innym przykładem może być ogólnie pojęta synchronizacja procesów, np. wzajemne wykluczanie – tu również mamy do czynienia z uzgadnianiem.<br>
            <br>
            <p>
              Problemy uzgadniania stają się bardzo trudne w systemach, w których mogą występować awarie. Klasycznym przykładem obrazującym możliwe trudności jest <b>problem</b> <b>dwu</b> <b>armii</b> . W problemie tym rozpatrywany jest atak dwóch armii niebieskich o sile 3000 pododdziałów każda, na armię czerwoną o sile 5000 pododdziałów. Armie niebieskie stacjonują w odległych miejscach i muszą wspólnie podjąć decyzję o ataku. Jedynie ich wspólny atak może zakończyć się zwycięstwem. Decyzja jest więc w tym przypadku binarna: atakować lub nie. Niestety komunikacja armii niebieskich wymaga wysyłania posłańców, którzy mogą być przechwyceni przez wroga – obrazuje to zawodny kanał komunikacyjny.
            </p>
            <br>
            <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-11-wyk-1.0-Slajd11 title=Sr-11-wyk-1.0-Slajd11> </a><br>
            <b style=COLOR:#3d85c6><font size=3>Problem dwu armii</font></b><br>
            <hr size=2>
          </div>
          <br>
        </div>
        <div id=xpp4 style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2598frcr4zdv_b.png" style=HEIGHT:344px;WIDTH:500px><br>
          <br>
          Kanały komunikacyjne w problemie dwu armii są zawodne. Każdy komunikat może być więc utracony. Załóżmy, że generał pierwszej armii niebieskiej wysyła posłańca z wiadomością „atakujemy” do generała drugiej armii. Ten odebrawszy propozycję, odsyła posłańca z wiadomością „ok, atakujemy”. Generał 1 dostaje potwierdzenie, ale zauważa, że generał 2 nie wie, że on dostał potwierdzenie, a więc że może nie wiedzieć czy przeprowadzić atak czy nie. W związku z tym wysyła drugiego posłańca potwierdzającego decyzję o ataku. Generał 2 po odebraniu wiadomości stwierdza, że generał 1 nie wie, że jego posłaniec dotarł z potwierdzeniem, a skoro nie dotarł to generał 2 może zwątpić w plany ataku. Na wszelki wypadek wysyła więc kolejnego posłańca do generała 1, potwierdzającego odbiór wiadomości o potwierdzeniu ataku... Łatwo zauważyć, że bez względu na liczbę przesyłanych komunikatów (posłańców), generałowie nigdy nie uzyskają całkowitej pewności co do podejmowanej decyzji. Wynika to z tego, że zawsze ostatni przesyłany komunikat nie będzie potwierdzany, a jeżeli nie ma pewności, że komunikat ten dotarł, to nie ma również pewności, że cały protokół podejmowania decyzji został zakończony. Pomimo więc bardzo prostej sytuacji modelowej – mamy tu do czynienia z dwoma poprawnymi procesami (generałowie) – nie można podjąć decyzji, ponieważ komunikacja jest zawodna.<br>
          <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-11-wyk-1.0-Slajd12 title=Sr-11-wyk-1.0-Slajd12> </a><br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Problem bizantyjskich generałów</font></b><br>
          <hr size=2><br>
          <div id=q0cq style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2599gbpnwxhn_b.png" style=HEIGHT:342px;WIDTH:500px><br>
            <br>
            Rozpatrzmy teraz przypadek, kiedy komunikacja jest niezawodna, ale procesy mogą ulegać dowolnym awariom. Klasycznym przykładem może być tutaj <b>problem</b> <b>bizantyjskich</b> <b>generałów</b> . W tym przykładzie również armia niebieska będzie atakować armię czerwoną, ale tym razem armia niebieska jest dowodzona przez <i>n</i> generałów, którzy muszą podjąć wspólnie decyzję. Do podjęcia decyzji jest potrzebna wiedza dotycząca liczebności podległych im oddziałów. Niestety <i>m</i> spośród wszystkich <i>n</i> generałów jest zdrajcami. Oznacza to, że ich odpowiedzi będą celowo nieprawdziwe i sprzeczne, próbując w ten sposób nie dopuścić do porozumienia się generałów lojalnych. Zakładamy tu dodatkowo, że generałowie zdrajcy nie współpracują.<br>
            <br>
            <p>
              Ze względu na przewidywane dowolne awarie procesów, należy w tym przypadku inaczej zdefiniować porozumienie. Generałowie dążą do ustalenia liczebności oddziałów i wymieniają te informacje między sobą. Porozumieniem jest ustalenie wektora liczebności oddziałów przez poszczególnych generałów, w taki sposób, że jeżeli <i>i-ty</i> generał jest lojalny, to <i>i-ta</i> pozycja wektora zawiera liczebność jego oddziału. W przeciwnym razie pozycja ta będzie nieokreślona.
            </p>
            <br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>Algorytm Lamporta i innych</font></b><br>
            <hr size=2>
          </div>
          <br>
        </div>
        <div id=rtu: style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2600ghxpfj6b_b.png" style=HEIGHT:342px;WIDTH:500px><br>
          <br>
          Jednym z algorytmów rozwiązujących problem bizantyjskich generałów jest algorytm Lamporta i innych. Jego idea polega na wstępnym rozesłaniu informacji o liczebności własnych oddziałów, a następnie na rozesłaniu informacji otrzymanych od innych generałów celem weryfikacji tak uzyskanych informacji.<br>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Algorytm Lamporta i innych - przykład</font></b><br>
          <hr size=2><br>
          <div id=z882 style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2601fpmbmcpr_b.png" style=HEIGHT:342px;WIDTH:500px><br>
            <br>
            Przykład na slajdzie pokazuje wykonanie algorytmu Lamporta dla 4 generałów, wśród których jeden jest zdrajcą, a więc <i>n=4</i> i <i>m=1</i> . Warto zwrócić uwagę, że generał 3, który jest zdrajcą odpowiada za każdym razem inaczej, rozsyłając nieprawdziwe informacje. Pomimo tego pozostali generałowie są w stanie poprawnie ustalić liczebność swoich oddziałów, przegłosowując generała-zdrajcę.<br>
            <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-11-wyk-1.0-Slajd15 title=Sr-11-wyk-1.0-Slajd15> </a><br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>Warunki osiągnięcia porozumienia</font></b><br>
            <hr size=2><br>
            <div id=vmp6 style=TEXT-ALIGN:left>
              <img src="images/dcjpvv6n_2602d7fx94dd_b.png" style=HEIGHT:344px;WIDTH:500px><br>
              <br>
              Algorytm Lamporta gwarantuje poprawne określenie liczebności oddziałów lojalnych generałów, ale nie gwarantuje wykrycia generałów-zdrajców. Jeżeli bowiem generał-zdrajca będzie konsekwentnie udostępniał te same informacje wszystkim innym generałom, to nie zostanie wykryta żadna niezgodność i wartość, którą podał będzie uznana za poprawną.<br>
              <br>
              <p>
                Zmniejszenie liczby generałów do <i>n=3</i> i pozostawienie jednego generała-zdrajcy spowoduje, że osiągnięcie porozumienia nie będzie możliwe. Udowodniono, że w systemie z <i>m</i> wadliwymi procesami porozumienie można osiągnąć wówczas, gdy istnieje <i>2m+1</i> procesów działających poprawnie, co daje ogólną liczbę <i>3m+1</i> generałów. Inaczej mówiąc, w systemie musi być co najmniej 2/3 procesów działających poprawnie.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                Osiągnięcie porozumienia może wiązać się z wieloma innymi problemami. W asynchronicznym systemie rozproszonym, a więc w takim, w którym nie można zagwarantować dostarczenia komunikatów w znanym i skończonym czasie, osiągnięcie porozumienia jest niemożliwe, jeżeli choć jeden proces jest wadliwy (chodzi o awarie uciszające). Powodem jest niemożliwość rozróżnienia procesów, które uległy znacznemu spowolnieniu (ale nadal są poprawne) od procesów które uległy awarii typu załamanie.
              </p>
              <br>
              <br>
              <b style=COLOR:#3d85c6><font size=3>Niezawodna komunikacja klient-serwer</font></b><br>
              <hr size=2>
            </div>
            <br>
          </div>
          <div id=d-ee style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2603fg7xrn6v_b.png" style=HEIGHT:343px;WIDTH:500px><br>
            <br>
            Komunikacja pomiędzy procesami w systemie rozproszonym najczęściej wykonywana jest za pośrednictwem niezawodnego, strumieniowego protokołu warstwy transportowej (np. TCP). Jest to wygodne, ponieważ protokół ten maskuje występowanie pewnych błędów, np. błędów ominięcia. Zagubienie komunikatu powoduje jego retransmisję, która jest całkowicie przezroczysta dla wyższej warstwy oprogramowania. Niektóre awarie jednak nie są maskowane. Z różnych powodów może dojść do załamania (zerwania) połączenia, co jest następnie sygnalizowane klientowi. Jedynym sposobem na maskowanie zerwanego połączenia mogłaby być automatyczna próba nawiązania go ponownie.<br>
            <br>
            <p>
              Na wyższym poziomie komunikacja może być realizowana z wykorzystanie zdalnych wywołań procedur (RPC) lub metod (RMI). Jedną z motywacji stosowania mechanizmu RPC było ukrywanie faktu rozproszenia wywołania procedury. Jeżeli w systemie występują awarie, to pojawiają się podczas przetwarzania sytuacje, które nie wystąpiłyby w przypadku lokalnego wywoływania procedur. Powoduje to, że zachowanie pełnej przezroczystości nie zawsze będzie możliwe. Błędy, które mogą się pojawić podczas realizacji zdalnego wywołania procedur można podzielić na 5 wymienionych klas.
            </p>
            <br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>RPC w sytuacjach awaryjnych</font></b><br>
            <hr size=2><br>
          </div>
          <div id=g94q style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2604frp7ftd9_b.png" style=HEIGHT:343px;WIDTH:500px><br>
            <br>
            Pierwsza kategoria błędów polega na niemożliwości odnalezienia serwera przez klienta. Niemożliwość taka może wynikać z problemów z lokalizacją serwera, jego wyłączeniem lub z zastosowaniem nowego interfejsu programowego. Serwer, który zmienia interfejs dostępu do usług dokonuje jednocześnie aktualizacji pieńka pośredniczącego w dostępie do niego. Klient stosujący stary pieniek nie będzie w takiej sytuacji w stanie dołączyć się do takiego serwera. Przedstawione typy błędów należy w jakiś sposób obsłużyć, najlepiej z zachowaniem przezroczystości wywołania metody. Jest to możliwe przy zastosowaniu mechanizmu wyjątków w nowszych językach programowania, takich jak język Java. W języku C można w tym samym celu zastosować np. sygnały.<br>
            <br>
            <p>
              Druga kategoria błędów występujących podczas realizacji zdalnych wywołań procedur to zaginięcie komunikatu z żądaniem klienta. Jest to kategoria, której poprawne obsłużenie jest najprostsze. Klient wysyłając komunikat z żądaniem ustawia czasomierz i po upływie ustalonego czasu uznaje, że komunikat nie dotarł do serwera, ponieważ nie odebrano odpowiedzi. W efekcie następuje retransmisja żądania. Jeżeli komunikat faktycznie został zagubiony, serwer obsłuży retransmitowane żądanie tak, jakby to był oryginał. Jeżeli komunikat jednak dotarł do serwera, to mechanizm wywołań zdalnych należy rozbudować o środki do wykrywania powielonych wywołań. W przypadku przeciążonego serwera klient może po kilku retransmisjach zrezygnować z wysyłania kolejnych. Następuje wtedy przejście do obsługi błędu typy „brak dostępu do serwera”.
            </p>
            <br>
            <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-11-wyk-1.0-Slajd18 title=Sr-11-wyk-1.0-Slajd18> </a><br>
            <div id=rzef style=TEXT-ALIGN:left>
              <img src="images/dcjpvv6n_26059fbk74gr_b.png" style=HEIGHT:341px;WIDTH:500px><br>
              <br>
              Załamanie serwera może nastąpić po obsłużeniu żądania lub przed. W zależności od tego czy żądanie zostało obsłużone czy nie, reakcja klienta powinna być różna. Jeżeli serwer nie przystąpił do obsługi odebranego żądania, to żądanie takie powinno zostać retransmitowane przez klienta. Jeżeli serwer obsłużył żądanie i uległ awarii to powinno to zostać zgłoszone po stronie klienta. Problem polega jednak na tym, że klient nie jest w stanie tych dwóch sytuacji rozróżnić. Jedyne co stwierdza to fakt upłynięcia czasu od momentu wysłania żądania.<br>
              <br>
              <p>
                Istnieje kilka metod reakcji na awarię serwera. Pierwsza metoda polega na oczekiwaniu na wznowienie pracy serwera i przesłaniu ponownego żądania w celu uzyskania odpowiedzi. Metoda ta określana jest jako <b>semantyka</b> <b>co</b> <b>najmniej</b> <b>jednokrotna</b> (ang. <i>at</i> <i>least</i> <i>once</i> <i>semantics</i> ). Gwarantuje ona, że każde wywołanie procedury zostanie wykonane przynajmniej jeden raz, ale być może, że również wiele razy. Drugie podejście polega na natychmiastowym przerwaniu prób komunikacji z serwerem po stwierdzeniu wystąpienia problemów. Jest to <b>semantyka</b> <b>co</b> <b>najwyżej</b> <b>jednokrotna</b> (ang. <i>at</i> <i>most</i> <i>once</i> <i>semantics</i> ), która gwarantuje, że wywołanie procedury nastąpi najwyżej raz, ale być może, że nie nastąpi w ogóle. Najprostszym rozwiązaniem jest oczywiście nie gwarantowanie niczego. W takiej sytuacji wywołanie zdalne mogło nie nastąpić, mogło nastąpić raz lub wielokrotnie.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                Oczywiście semantyki te nie są tym, czego oczekuje klient. Użytkownik oczekuje tak naprawdę <b>semantyki</b> <b>dokładnie</b> <b>jednokrotnej</b> (ang. <i>exactly</i> <i>once</i> <i>semantics</i> ). Niestety semantyka taka jest niemożliwa do zrealizowania.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                Podsumowując: możliwość załamania serwera wyraźnie różnicuje systemy scentralizowane i rozproszone w kontekście wykonywania procedur. W przypadku systemów scentralizowanych awaria serwera pociąga za sobą awarię klienta. W systemach rozproszonych awaria serwera wymaga obsłużenia tej sytuacji po stronie klienta.
              </p>
              <br>
              <br>
              <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-11-wyk-1.0-Slajd19 title=Sr-11-wyk-1.0-Slajd19> </a>
              <div id=ewex style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2606fx994wdb_b.png" style=HEIGHT:339px;WIDTH:500px><br>
                <br>
                Klient nie odbierając potwierdzenia ze strony serwera nie ma możliwości poprawnego ocenienia zaistniałej sytuacji. Powodem braku odpowiedzi może bowiem być zaginięcie komunikatu z odpowiedzią potwierdzającą wykonanie operacji, ale równie dobrze źródłem braku odpowiedzi może być znaczące spowolnienie pracy przez serwer. Jedyną sensowną reakcją ze strony klienta jest w tym przypadku retransmisja żądania. Poprzednie zlecenie być może jednak dotarło do serwera i po retransmisji zostanie wykonane ponownie. W przypadku pewnych zleceń nie jest to problemem. Np. zlecenie odczytu fragmentu pliku od określonej pozycji, przy założeniu braku współbieżnego zapisu, zawsze da ten sam rezultat. Operacje takie są określane jako operacje <b>idempotentne</b> (ang. <i>idempotent</i> ). Wiele operacji nie jest jednak idempotentnych. Np. usunięcie pliku przy ponownej próbie wykonania zwróci błąd, ponieważ pliku już nie będzie istniał. Podobnie wygląda sytuacja z tworzeniem nowego pliku. Rozwiązaniem jest numerowanie zleceń pochodzących od poszczególnych klientów. Serwer przed wykonaniem zlecenia sprawdza czy dane żądanie, pochodzące od konkretnego klienta, zostało już zrealizowane czy nie. Jeżeli było, to odsyła jedynie potwierdzenie, nie wykonując samej operacji. Dodatkowym zabezpieczeniem może być sygnalizowanie serwerowi, że dane żądanie jest retransmitowane, co powinno wzmóc czujność serwera. Rozwiązania te niestety wymuszają przechowywanie po stronie serwera informacji o klientach w postaci numerów ostatnio zrealizowanych zleceń. Informacje te będą niestety tracone przy ewentualnej awarii serwera.
                <p>
                  <br>
                </p>
                <p>
                  Kolejnym problemem pojawiającym się podczas wykonywania zdalnych wywołań metod jest awaria klienta następująca po zleceniu zdalnego przetwarzania. Obliczenia zainicjowanie przez klienta mogą pozostać aktywne po stronie serwera niepotrzebnie go obciążając. Takie pozostałości nazywane są <b>sierotami</b> (ang. <i>orphan</i> ). Sieroty mogą powodować problemy jeżeli np. powodowały zajmowanie zasobów. Również komunikaty zwrotne po zakończeniu przetwarzania mogą być mylące dla klienta, który wznowił swoje przetwarzania.<br>
                </p>
                <p>
                  <br>
                </p>
                <p>
                  Istnieje kilka metod radzenia sobie z sierotami. Pierwsza, zwana <b>eksterminacją</b> (ang. <i>extermination</i> ), polega na rejestrowaniu w pamięci trwałej (dysk) wszystkich zleceń przez namiastkę klienta i jawnym usuwaniu odpowiedzi-sierot. Wadą tego rozwiązania jest bardzo duży koszt związany z rejestrowaniem wywołań. Drugie rozwiązanie, zwane <b>reinkarnacją</b> (ang. <i>reincarnation</i> ), polega na oznaczaniu każdego wywołania numerem epoki, oznaczającej logicznie upływający czas pomiędzy kolejnymi wznowieniami pracy klienta. Po wznowieniu pracy klient wysyła do wszystkich serwerów komunikat o nastaniu nowej epoki, który powoduje zatrzymanie wszystkich obliczeń tego klienta. Jeżeli jakaś sierota przeżyje na serwerze, do którego aktualnie nie ma dostępu, to i tak będzie mogła być łatwo wykryta poprzez stwierdzenie nieaktualnego numeru epoki. W łagodnej wersji reinkarnacji (ang. <i>gentle</i> <i>reincarnation</i> ), serwer po odebraniu komunikatu o nastaniu nowej epoki próbuje ustalić właścicieli każdej z wykonywanych prac. Usuwane są tylko te zadania, dla których nie udało się ustalić właściciela. Ostatnią propozycją jest przydział ustalonego kwantu czasu zdalnej procedurze na jej wykonanie. Przekroczenie tego czasu jest możliwe tylko po uzyskaniu potwierdzenia od klienta. Jeżeli klient ulegnie awarii, potwierdzenie nie zostanie udzielone i automatycznie zadanie takie ulegnie anulowaniu. Metoda ta jest nazywana <b>wygaśnięciem</b> (ang. <i>expiration</i> ).
                </p>
                <br>
                <br>
                <b style=COLOR:#3d85c6><font size=3>Zatwierdzanie rozproszone</font></b><br>
                <hr size=2><br>
              </div>
              <div id=tzfb style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2607gtsm98gk_b.png" style=HEIGHT:343px;WIDTH:500px><br>
                <br>
                Zatwierdzanie rozproszone (ang. <i>distributed</i> <i>commit</i> ) jest ogólnym problemem, w którym chodzi o wykonanie danej operacji przez każdego członka grupy procesów lub przez żadnego. Problem niezawodnego rozsyłania jest przykładem problemu zatwierdzania rozproszonego, w którym operacją, która ma być wykonana przez wszystkich (lub przez nikogo) jest dostarczenie konkretnej wiadomości.<br>
                <br>
                <p>
                  Zatwierdzanie rozproszone b. często odbywa się przy udziale koordynatora. W najprostszym przypadku koordynator informuje procesy czy mają dokonać lokalnego zatwierdzenia wykonywanych operacji (np. transakcji). Podejście to określane jest jako <b>protokół</b> <b>zatwierdzania</b> <b>jednofazowego</b> (ang. <i>one-phase</i> <i>commit</i> <i>protocol</i> ). W podejściu tym nie uwzględnia się sytuacji, w której lokalne zatwierdzenie operacji nie będzie możliwe, np. ze względu na zablokowane zasoby. W przypadku zatwierdzania rozproszonego potrzebne są więc bardziej rozbudowane schematy, np. <b>protokół</b> <b>zatwierdzania</b> <b>dwufazowego</b> .
                </p>
                <br>
                <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-11-wyk-1.0-Slajd21 title=Sr-11-wyk-1.0-Slajd21> </a><br>
                <b style=COLOR:#3d85c6><font size=3>Protokół zatwierdzania dwufazowego - 2PC</font></b><br>
                <hr size=2>
              </div>
              <br>
            </div>
            <div id=u0zy style=TEXT-ALIGN:left>
              <img src="images/dcjpvv6n_2608dh4mm2gf_b.png" style=HEIGHT:343px;WIDTH:500px><br>
              <br>
              <b>Protokół</b> <b>zatwierdzania</b> <b>dwufazowego</b> (ang. <i>two-phase</i> <i>commit</i> <i>protocol</i> ) uwzględnia fakt, że lokalne zatwierdzenie transakcji nie zawsze będzie możliwe. W związku z tym, przed zatwierdzeniem transakcji realizowane jest głosowanie mające na celu ustalenie czy wszyscy uczestnicy przetwarzania będą mogli transakcję zatwierdzić. Koordynator wysyła w tym celu komunikat <i>GŁOSOWANIE</i> do wszystkich uczestników przetwarzania, rozpoczynając w ten sposób głosownie. Uczestnik głosowania odpowiada komunikatem <i>ZA</i> lub <i>PRZECIW</i> , w zależności od tego czy może zatwierdzić operację lokalnie czy nie. Koordynator po odebraniu wyników głosowania podejmuje decyzję. Jeżeli wszyscy głosowali na tak, wysyła komunikat <i>ZATWIERDŹ</i> , powodujący globalne zatwierdzenie transakcji. Jeżeli pojawił się choć jeden głos na nie, wysyłany jest komunikat <i>ZANIECHAJ</i> . Uczestnicy przetwarzania, którzy głosowali na tak, po odebraniu komunikatu <i>ZATWIERDŹ</i> dokonują lokalnego zatwierdzenie transakcji. Jeżeli uczestnik głosował na nie, lub otrzymał komunikat <i>ZANIECHAJ</i> , dokonuje wycofania transakcji.<br>
              <br>
              <br>
              <b style=COLOR:#3d85c6><font size=3>Stany w protokole 2PC</font></b><br>
              <hr size=2><br>
              <div id=ktcd style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2609c9ndmqft_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                <br>
                <p>
                  Podstawową wadą protokołu 2PC jest jego wrażliwość na awarie, zarówno koordynatora jak i poszczególnych uczestników. W przetwarzaniu zarówno po stronie koordynatora jak i uczestników występują stany oczekiwania na komunikat (CZEKANIE u koordynatora, ROZPOCZĘCIE i GOTOWOŚĆ u uczestnika). Awaria któregoś z procesów może powodować w tym przypadku zablokowanie pozostałych, a więc prowadzi do niepowodzenia protokołu jako całości. W celu rozwiązania tego problemu można zastosować odliczanie czasu celem wykrycia awarii.<br>
                </p>
                <p>
                  <br>
                </p>
                <p>
                  Uczestnik głosowania czeka na początku w stanie ROZPOCZĘCIE na komunikat GŁOSOWANIE. Jeżeli komunikat nie nadchodzi, uznaje, że transakcję należy wycofać. Jeżeli komunikat jednak nadejdzie, odeśle odpowiedź PRZECIW.<br>
                </p>
                <p>
                  <br>
                </p>
                <p>
                  Koordynator jest blokowany w stanie CZEKANIE. Jeżeli w określonym czasie nie otrzyma odpowiedzi od wszystkich uczestników, podejmuje decyzję o wycofaniu transakcji (wyśle komunikat <i>ZANIECHAJ</i> ).<br>
                </p>
                <p>
                  <br>
                </p>
                <p>
                  Uczestnik może być także blokowany w stanie GOTOWOŚĆ. Jeżeli nie nadejdzie komunikat od koordynatora, to uczestnik może podjąć decyzję o wycofaniu transakcji. Lepszym rozwiązaniem jest jednak próba skomunikowania się z innymi uczestnikami w celu uzyskania informacji o decyzji koordynatora. Jeżeli uczestnik <i>P</i> dowie się od innego uczestnika <i>Q</i> , że on przeszedł do stanu ZATWIERDZENIE, to <i>P</i> również może zatwierdzić transakcję, ponieważ jedynym sposobem na przejście do stanu ZATWIERDZENIE jest uzyskanie od koordynatora komunikatu <i>ZATWIERDŹ</i> wskazującego na taką decyzję koordynatora (komunikat <i>ZATWIERDŹ</i> nie dotarł po prostu do <i>P</i> ). Podobnie jeżeli <i>Q</i> jest w stanie <i>ZANIECHANIE</i> , to <i>P</i> również może bez obaw wycofać swoją lokalną transakcję.<br>
                </p>
                <p>
                  <br>
                </p>
                <p>
                  Sytuacja jest trudniejsza, gdy proces <i>Q</i> jest w stanie ROZPOCZĘCIE. Oznacza to, że <i>Q</i> nie dostał od koordynatora komunikatu <i>GŁOSOWANIE</i> . W takiej sytuacji bezpieczniej jest przejść w obu procesach do stanu ZANIECHANIE.<br>
                </p>
                <p>
                  <br>
                </p>
                <p>
                  Najtrudniejsza sytuacja jest wtedy, gdy <i>Q</i> jest w stanie GOTOWOŚĆ, również czekając na decyzję od koordynatora. Mogło się zdarzyć, że koordynator uległ awarii po zainicjowaniu głosowania i wszystkie procesy są w stanie oczekiwania. Nawet jeżeli wszystkie są gotowe do zatwierdzenia, to i tak nie uda się podjąć żadnej decyzji – trzeba czekać na wznowienie pracy koordynatora.
                </p>
                <br>
                <br>
                <b style=COLOR:#3d85c6><font size=3>Protokół 2PC z rekonstrukcją - koordynator</font></b><br>
                <hr size=2><a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-11-wyk-1.0-Slajd23 title=Sr-11-wyk-1.0-Slajd23> </a><br>
              </div>
              <div id=yv_x style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2610htvrmqc3_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                <br>
                Slajd przedstawia działania protokołu 2PC zakładającego możliwość rekonstrukcji (odtwarzania stanu) procesów. Rekonstrukcja procesu wymaga zapisywania jego stanu do pamięci trwałej (np. dysk), dlatego wszystkie zmiany stanów w procesach są najpierw zapisywane do lokalnego rejestru, a następnie dopiero wykonywane.<br>
                <br>
                <p>
                  Proces koordynatora rozsyła do wszystkich komunikat <i>GŁOSOWANIE</i> i oczekuje na odpowiedzi. Brak odpowiedzi (przekroczenie czasu oczekiwania) powoduje, że zapada decyzja o wycofaniu transakcji (linia 6). Jeżeli wszyscy odpowiedzą pozytywnie, transakcja jest zatwierdzana. W przeciwnym wypadku następuje jej wycofanie poprzez rozesłanie komunikatu <i>ZANIECHAJ</i> .
                </p>
                <br>
                <br>
                <b style=COLOR:#3d85c6><font size=3>Protokół 2PC z rekonstrukcją - uczestnik</font></b><br>
                <hr size=2><a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-11-wyk-1.0-Slajd24 title=Sr-11-wyk-1.0-Slajd24> </a><br>
              </div>
              <div id=q5t2 style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2611ckkhstd3_b.png" style=HEIGHT:340px;WIDTH:500px><br>
                <br>
                Jeżeli proces uczestnika w momencie zajścia awarii był w stanie ROZPOCZĘCIE i nie podjął jeszcze decyzji o zatwierdzeniu transakcji, to może ją po prostu wycofać po odtworzeniu stanu. Jeżeli zdążył przejść do stanu ZATWIERDZENIE lub ZANIECHANIE, to powinien zostać odtworzony właśnie do tego stanu. Problematyczne staje się załamanie w stanie GOTOWOŚCI. W tym przypadku proces nie jest w stanie sam zadecydować co powinien zrobić dalej. Musi skontaktować się z innymi uczestnikami, w celu zadecydowania o losie lokalnej transakcji. Sytuacja jest analogiczna do braku odpowiedzi od koordynatora po zainicjowaniu głosowania (linia 9).<br>
                <br>
                <p>
                  Decyzja o zatwierdzeniu transakcji w normalnych warunkach przychodzi od koordynatora. Jeżeli jednak on nie odpowiada, można próbować uzyskać informacje o decyzji od innych uczestników – następuje wysłanie komunikatu do wszystkich uczestników w linii 10. Decyzja, która nadejdzie jest zapisywana i ostatecznie egzekwowana.<br>
                </p>
                <p>
                  <br>
                </p>
                <p>
                  Jeżeli proces głosuje na nie w głosowaniu, lub zapada decyzja o odrzuceniu transakcji (komunikat <i>ZANIECHAJ</i> bezpośrednio od koordynatora lub pośrednio od innych uczestników), transakcja jest wycofywana.
                </p>
                <br>
                <br>
                <b style=COLOR:#3d85c6><font size=3>Obsługa pytania o decyzję</font></b><br>
                <hr size=2><br>
              </div>
              <div id=e3je style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2612ctfbnjgq_b.png" style=HEIGHT:341px;WIDTH:500px>
              </div>
              <br>
            </div>
          </div>
          Każdy z procesów musi być gotowy na udzielenie odpowiedzi innym uczestnikom o decyzji w sprawie zatwierdzenia transakcji. Działanie takie może być realizowane przez oddzielny wątek, którego zadaniem jest tylko udzielanie odpowiedzi na komunikat <i>PYTANIE_O_DECYZJĘ</i> . Odpowiedź jest udzielana tylko wtedy, gdy jest znana, a więc gdy ostatni stan zapisany w rejestrze jest stanem końcowym <i>ZATWIERDZENIE</i> lub <i>ZANIECHANIE</i> . Odpowiedź negatywna jest udzielana również wtedy, gdy proces w momencie odbioru pytania o stan nadal pozostaje w stanie <i>ROZPOCZĘCIE</i> , co oznacza, że nie dostał jeszcze komunikatu <i>GŁOSOWANIE</i> od koordynatora, a to może oznaczać awarię koordynatora. Jeżeli odpytywany proces pozostaje nadal w stanie <i>GOTOWOŚĆI</i> <i>,</i> to ignoruje zapytanie i nie odpowiada, ponieważ sam nie zna jeszcze decyzji o losach transakcji. W skrajnym przypadku może się zdarzyć, że wszyscy uczestnicy nie dostaną komunikatu z decyzją od koordynatora, ponieważ ten ulegnie awarii. Wszyscy będą więc w stanie <i>GOTOWOŚCI</i> , a więc nie będą odpowiadać na pytania o decyzję. W efekcie nastąpi zablokowanie wszystkich uczestników do czasu rekonstrukcji procesu koordynatora, który po wznowieniu pracy podejmie decyzję. Z powodu tego blokowania protokół 2PC bywa również nazywany <b>blokującym</b> <b>protokołem</b> <b>zatwierdzania</b> (ang. <i>blocking</i> <i>commit</i> <i>protocol</i> ).<br>
          <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-11-wyk-1.0-Slajd26 title=Sr-11-wyk-1.0-Slajd26> </a><br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Zatwierdzanie trzyfazowe</font></b><br>
          <hr size=2><br>
        </div>
        <div id=m6d7 style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2613djswxkhs_b.png" style=HEIGHT:343px;WIDTH:500px><br>
          <br>
        </div>
        Podstawową wadą zatwierdzania dwufazowego (2PC) jest niemożliwość dojścia do decyzji w przypadku awarii koordynatora. Uczestnicy przetwarzania muszą czekać blokująco na wznowienie pracy przez niego. Problem ten został rozwiązany w <b>protokole</b> <b>zatwierdzania</b> <b>trzyfazowego</b> (ang. <i>three-phase</i> <i>commit</i> <i>protocol</i> – 3PC). Protokół 3PC wprowadza dodatkową fazę przetwarzania, pomiędzy fazę głosowania i ostatecznego zatwierdzania. W fazie tej następuje częściowe, wstępne zatwierdzenie transakcji, które dopiero w następnej fazie powoduje ostateczne zatwierdzenie.<br>
        <br>
        <br>
        <b style=COLOR:#3d85c6><font size=3>Stany w protokole 3PC</font></b><br>
        <hr size=2><br>
        <div id=xft3 style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2614gzcrd6c2_b.png" style=HEIGHT:341px;WIDTH:500px><br>
          <br>
          Slajd przedstawia maszyny stanowe dla protokołu 3PC. Istotą protokołu 3PC jest to, że:<br>
          <br>
          <ol>
            <li>
              Zarówno w przypadku koordynatora jak i uczestnika nie istnieje taki stan, z którego można by przejść bezpośrednio do stanu ZATWIERDZENIA albo ZANIECHANIA (np. stan CZEKANIE umożliwia przejście do ZANIECHANIE albo WSTĘPNE_ZATWIERDZENIE).
            </li>
            <li>
              Nie istnieje stan, w którym nie można by podjąć ostatecznej decyzji i z którego można by przejść do stanu ZATWIERDZENIA.
            </li>
            <li>
              <br>
            </li>
          </ol>
          <p>
            Warunki te, jak wykazano, są konieczne i dostateczne do tego, żeby uzyskać protokół nieblokujący.
          </p>
          <p>
            <br>
          </p>
          <p>
            Jeżeli koordynator zablokuje się w stanie CZEKANIE, to zadecyduje o wycofaniu transakcji, ponieważ jeden z procesów uległ awarii. Jeżeli blokowanie nastąpi w stanie WSTĘPNE_ZATWIERDZENIE, to przekroczeniu czasu oczekiwania nastąpi zatwierdzenie transakcji, bo wiadomo, że proces, który uległ awarii głosował za zatwierdzeniem. Uczestnik, który uległ awarii po rekonstrukcji będzie mógł transakcję zatwierdzić.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Uczestnik może zablokować się w stanie GOTOWOŚCI lub WSTĘPNEGO_ZATWIERDZENIA. Po przekroczeniu czasu oczekiwania na odpowiedź od koordynatora przystąpi do próby uzyskania decyzji od innych uczestników. Jeżeli inny uczestnik jest w stanie ZATWIERDZENIA lub ZANIECHANIA, to stan ten powinien zostać przejęty przez zablokowanego uczestnika. Jeśli wszyscy uczestnicy są w stanie ZATWIERDZENIA_WSTĘPNEGO, to transakcja może być zatwierdzona. Uczestnik zablokowany w stanie ROZPOCZĘCIE może transakcję wycofać. Jeżeli jakiś uczestnik nadal jest w stanie ROZPOCZĘCIA, to znaczy, że żaden inny uczestnik nie jest w stanie WSTĘPNEGO_ZATWIERDZENIA.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Jeżeli uczestnik jest zablokowany w stanie GOTOWOŚCI i również większość innych uczestników jest w stanie GOTOWOŚCI, to transakcja może być zaniechana. Inny uczestnik, który mógł w tym czasie ulec awarii, nawet jeżeli dotarł do stanu WSTĘPNEGO_ZATWIERDZENIA może po rekonstrukcji wycofać swoją transakcję. W przypadku protokołu 2PC proces mógł po rekonstrukcji wrócić do stanu ZATWIERDZENIA, podczas gdy inni byli nadal w stanie GOTOWOŚCI. Do czasu zrekonstruowania procesu, pozostali uczestnicy protokołu 2PC nie mogli podjąć decyzji. W przypadku protokołu 3PC wiadomo, że rekonstrukcja będzie kończyła się stanem ROZPOCZĘCIE, ZANIECHANIE lub WSTĘPNE_ZATWIERDZENIE, dlatego pozostałe poprawne procesy mogą uzgodnić ostateczną decyzję.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Jeżeli uczestnik jest zablokowany w stanie WSTĘPNEGO_ZATWIERDZENIA, a większość pozostałych uczestników jest również w stanie WSTĘPNEGO_ZATWIERDZENIA, to transakcję można bezpiecznie zatwierdzić. Pozostałe procesy, które uległy awarii będą po rekonstrukcji w stanie GOTOWOŚCI, WSTĘPNEGO_ZATWIERDZENIA lub ZATWIERDZENIA.
          </p>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Odtwarzanie (rekonstrukcja)</font></b><br>
          <hr size=2><br>
        </div>
        <div id=t7do style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2615gbjvt6f4_b.png" style=HEIGHT:342px;WIDTH:500px><br>
          <br>
          Odtwarzanie (rekonstrukcja) ma na celu sprowadzenie procesu czy części systemu do stanu sprzed awarii. Generalnie istnieją dwie metody odtwarzania stanu: odtwarzanie wsteczne i odtwarzanie postępowe.<br>
          <br>
          <p>
            <b>Odtwarzanie</b> <b>wsteczne</b> (ang. <i>backward</i> <i>recovery</i> ) polega na wycofaniu systemu z aktualnego, błędnego stanu do stanu wcześniejszego, który był poprawny. Wykonanie takiego odtwarzania wymaga okresowego zachowywania stanu systemu i w przypadku awarii jego odtworzenie. Stan jest utrwalany w postaci tzw. <b>punktu</b> <b>kontrolnego</b> (ang. <i>checkpoint</i> ).<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            <b>Odtwarzanie</b> <b>postępowe</b> (ang. <i>forward</i> <i>recovery</i> ) polega na przeprowadzeniu systemu z aktualnego, błędnego stanu do nowego, poprawnego stanu, od którego system będzie mógł kontynuować swoją pracę. Główną trudnością odtwarzania postępowego jest konieczność znajomości błędów jakie mogą wystąpić. Umożliwia to zaimplementowanie odpowiednich procedur korygujących te błędy.
          </p>
          <p>
            Przykładem odtwarzania wstecznego jest retransmisja pakietu. Następuje w tym przypadku niejako wycofanie do sytuacji sprzed nadania komunikatu i powtórzenie tej operacji.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Przykładem odtwarzania postępowego jest kodowanie korekcyjne w protokołach transmisyjnych. Protokoły takie kodują dane nadmiarowo, dzięki czemu utraconą część danych (pojedynczy blok) można zrekonstruować z danych przesyłanych w otoczeniu felernego fragmentu.
          </p>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Problemy odtwarzania</font></b><br>
          <hr size=2><br>
          <div id=cn7a style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2616gxdw2rfx_b.png" style=HEIGHT:340px;WIDTH:500px><br>
            <br>
            Odtworzenie poprzedniego stanu po błędzie jest operacją bardzo kosztowną, podobnie jak i samo okresowe rejestrowanie stanu przetwarzania. Co gorsze: poniesienie tych kosztów nie zawsze gwarantuje sukces, ponieważ ten sam błąd może wystąpić ponownie. Całkowite maskowanie pewnych błędów nie będzie więc możliwe, gdyż groziłoby zapętleniem operacji odtwarzania stanu.<br>
            <br>
            <p>
              Innym problemem wstecznego odtwarzania jest niemożliwość wycofania pewnych operacji, szczególnie jeśli dotyczą one świata zewnętrznego.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Tworzenie punktów kontrolnych również jest dużym obciążeniem dla systemu. W przeciwieństwie do samej operacji odtwarzania, która wykonywana jest w momencie zajścia awarii, tworzenie punktów kontrolnych musi być realizowane nieustannie i to możliwie często. Z tego względu chętnie łączy się metodę odtwarzania wstecznego z rejestrowaniem komunikatów (ang. <i>message</i> <i>logging</i> ). Rejestrowanie może się odbywać po stronie nadawcy (ang. <i>sender-based</i> <i>logging</i> ) lub po stronie odbiorcy (ang. <i>receiver-based</i> <i>logging</i> ). W przypadku wystąpienia załamania procesu można wycofać go do ostatniego punktu kontrolnego i dostarczyć aplikacji wiadomości, które były do niej dostarczone od momentu utworzenia tego punktu kontrolnego. W ten sposób można dokonać odtworzenia pojedynczego procesu bez konieczności wycofywania przetwarzania innych procesów systemu rozproszonego.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Rejestrowanie komunikatów ma dodatkową zaletę w postaci zachowania determinizmu przetwarzania. W systemie rozproszonym kolejność dostarczania komunikatów może być za każdym razem inna, co może powodować, że powtórne wykonanie tego samego programu da inny efekt. Wycofanie procesu i dostarczenie mu tych samych komunikatów pozwala na zachowanie spójności przetwarzania względem innych procesów.
            </p>
            <br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>Punkty kontrolne</font></b><br>
            <hr size=2><br>
          </div>
          <div id=wr6t style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2617fg3chwpg_b.png" style=HEIGHT:342px;WIDTH:500px><br>
            <br>
            Wykonanie wstecznego odtwarzania jest możliwe pod warunkiem posiadania dostępu do punktów kontrolnych. System okresowo tworzy więc punkty kontrolne w poszczególnych węzłach i zapisuje je do lokalnej pamięci trwałej (ang. <i>stable</i> <i>storage</i> ). Odtworzenie stanu po awarii wymaga skonstruowania spójnego stanu globalnego na podstawie stanów lokalnych (punktów kontrolnych). Spójność oznacza tu oczywiście, że fakt zarejestrowania odbioru wiadomości <i>m</i> powinien pociągać za sobą zarejestrowanie faktu wysłania wiadomości <i>m</i> . Dokonując odtwarzania systemu najlepiej posłużyć się najwcześniejszymi punktami kontrolnymi, takimi które będą dawały w sumie spójny obraz. Takie odcięcie nazywamy <b>linią</b> <b>odtwarzania</b> (ang. <i>recovery</i> <i>line</i> ). Linia odtwarzania jest więc najnowszym odcięciem spójnym.<br>
            <br>
            <p>
              Na rysunku odcięcie stworzone przez ostatnie punkty kontrolne nie jest spójne, a więc nie może być wykorzystane do odtworzenia stanu. Wcześniejsza para punktów kontrolnych daje już spójne odcięcie i tworzy linię odtwarzania.
            </p>
            <br>
            <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-11-wyk-1.0-Slajd31 title=Sr-11-wyk-1.0-Slajd31> </a><br>
            <b style=COLOR:#3d85c6><font size=3>Niezależne punkty kontrolne</font></b><br>
            <hr size=2><br>
          </div>
          <div id=hkir style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2618cxw938fz_b.png" style=HEIGHT:340px;WIDTH:500px><br>
            <br>
            Punkty kontrolne można zapisywać w sposób skoordynowany lub nie. <b>Niezależne</b> <b>rejestrowanie</b> <b>punktów</b> <b>kontrolnych</b> (ang. <i>independent</i> <i>checkpointing</i> ) jest wygodne, ponieważ punkty kontrolne mogą być rejestrowane bez konieczności synchronizowania ze sobą rozproszonych procesów. Z drugiej jednak strony wymusza poszukiwanie linii rekonstrukcji w momencie zaistnienia awarii. Poszukiwanie takiego spójnego odcięcia wymaga rejestrowania zależności pomiędzy poszczególnymi punktami kontrolnymi w celu wykrycia niespójności. Samo znalezienie linii rekonstrukcji również nie jest trywialne. Co gorsze: poszukiwanie odcięcia spójnego może prowadzić do odrzucania kolejnych punktów kontrolnych. Sytuacja taka jest przedstawiona na rysunku. Pary punktów kontrolnych C13-C23 nie można wykorzystać, ponieważ punkt kontrolny C23 obejmuje zdarzenie odbioru wiadomości m6, a punkt kontrolny C13 nie obejmuje wysłania wiadomości m6. Cofając się w czasie, para C13-C22 również nie spełnia wymagań, ponieważ C13 obejmuje odbiór m5 a C22 nie obejmuje nadania m5. Podobnie pary C22-C12, C12-C21 i C21-C11. Ostatecznie więc stan początkowy przetwarzania pozwala uzyskać odcięcie spójne. Takie kaskadowe wycofywanie się nazywamy <b>efektem</b> <b>domina</b> (ang. <i>domino</i> <i>effect</i> ). Okazuje się jednak, że podstawowym problemem odtwarzania niezależnego jest koszt przechowywania punktów kontrolnych. Każdy punkt kontrolny zajmuje dużą ilość pamięci a przechowywać trzeba wiele takich punktów. Pamięć taką można oczyszczać ze starych punktów kontrolnych, ale jest to znów operacja kosztowna, wymagająca zastosowania rozproszonego algorytmu odśmiecania.<br>
            <br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>Koordynowane punkty kontrolne</font></b><br>
            <hr size=2><br>
            <div id=vt.u style=TEXT-ALIGN:left>
              <img src="images/dcjpvv6n_2619hpnkhngq_b.png" style=HEIGHT:343px;WIDTH:500px><br>
              <br>
              <b>Koordynowane</b> <b>rejestrowanie</b> <b>punktów</b> <b>kontrolnych</b> (ang. <i>coordinated</i> <i>checkpointing</i> ) polega na zsynchronizowaniu grupy procesów w celu zapamiętania swojego stanu w pamięci trwałej. Poniesienie kosztu synchronizacji jest opłacalne, ponieważ automatycznie tak wygenerowany zbiór punktów kontrolnych tworzy linię odtwarzania. Nie ma więc potrzeby przechowywania wielu punktów kontrolnych w węzłach, ponieważ zbiór ostatnich punktów kontrolnych automatycznie tworzy odcięcie spójne. Do skoordynowania procesów można wykorzystać algorytm rejestrowania stanu globalnego systemu. Innym, prostszym rozwiązaniem jest zastosowanie protokołu blokowania dwufazowego (2PC). W pierwszej fazie wykonywane jest zarejestrowanie punktów kontrolnych w poszczególnych węzłach po odebraniu zlecenia od koordynatora. Jednocześnie następuje wstrzymanie wysyłania nowych komunikatów. W drugiej fazie, po zebraniu potwierdzeń od wszystkich węzłów, koordynator wysyła zezwolenie na kontynuację przetwarzania. Algorytm pozwala na zarejestrowanie globalnie spójnego stanu, ponieważ po zarejestrowaniu stanu na węźle, węzeł ten przestaje nadawać nowe komunikaty do czasu zarejestrowania stanu w pozostałych węzłach. Eliminowane są więc automatycznie wiadomości, które potencjalnie mogłyby naruszyć spójność obrazu.<br>
              <br>
              <p>
                Podejście to można zoptymalizować poprzez rozsyłanie zlecenia na wykonanie punktu kontrolnego tylko do węzłów, które są <i>zależne</i> od koordynatora. Węzeł jest zależny od koordynatora, gdy odebrał wiadomość przyczynowo zależną od dowolnej wiadomości wysłanej przez koordynatora od czasu wykonania ostatniego punktu kontrolnego. Wykonanie <b>migawki</b> <b>przyrostowej</b> (ang. <i>incremental</i> <i>snaphot</i> ) realizowane jest poprzez wysłanie przez koordynatora zlecenia wykonania punktu kontrolnego do wszystkich procesów, do których wysyłał wiadomość od ostatniego punktu kontrolnego. Każdy proces, który dostaje takie zlecenie propaguje je jednokrotnie do wszystkich procesów, do których sam wysyłał wiadomość. Po zidentyfikowaniu grupy procesów zależnych od koordynatora wykonywane jest zarejestrowanie punktów kontrolnych w tych procesach podobnie jak to miało miejsce w przypadku standardowego 2PC.
              </p>
              <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-11-wyk-1.0-Slajd33 title=Sr-11-wyk-1.0-Slajd33></a><br>
            </div>
          </div>
        </div>
      </div>
    </div>
  </div>
</div>
<br></body>
</html>